#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
#include <time.h>
using namespace std;
// g++ tmp.cc -o tmp.exe


// 把list的数据拷给vector 利用vector进行sort 再拷回去 
// 使用库里的sort比使用list.sort()快
void test_ltovtol_vs_v()
{
	srand(time(0));
	const int N = 1000000;

	vector<int> v;
	v.reserve(N);

	list<int> lt1;
	list<int> lt2;

	for (int i = 0; i < N; ++i)
	{
		auto e = rand();
		lt1.push_back(e);
		lt2.push_back(e);
	}

	int begin1 = clock();

	for (auto e : lt1)
	{
		v.push_back(e);
	}

	sort(v.begin(), v.end());

	size_t i = 0;
	for (auto& e : lt1)
	{
		e = v[i++];
	}

	int end1 = clock();

	int begin2 = clock();
	lt2.sort();
	int end2 = clock();

	printf("copy vector sort:%d\n", end1 - begin1);
	printf("list sort:%d\n", end2 - begin2);
}

// sort() 比 list.sort() 快
void test_l_vs_v()
{
	srand(time(0));
	const int N = 100000;
	vector<int> v;
	v.reserve(N);

	list<int> lt;

	for (int i = 0; i < N; ++i)
	{
		auto e = rand();
		v.push_back(e);
		lt.push_back(e);
	}

	int begin1 = clock();
	sort(v.begin(), v.end());
	int end1 = clock();

	int begin2 = clock();
	lt.sort();
	int end2 = clock();

	printf("sort(v.begin(), v.end()):%d\n", end1 - begin1);
	printf("list.sort():%d\n", end2 - begin2);
}
int main()
{
	test_ltovtol_vs_v();
	//test_l_vs_v();

	return 0;
}
